package com.cskaoyan.com.queue;

/**
 * 使用数组(循环)数组, 实现一个数据结构为队列的数据容器/集合类
 */
public class MyArrayQueue <T> {

    private static final int MAX_CAPACITY = Integer.MAX_VALUE - 8;
    private static final int INIT_CAPACITY = 10;
    private Object[] objs; // 底层的循环数组
    private int size;      // 记录存储是元素数目
    private int head;      // 队列头下标标记
    private int end;       // 队列的尾的下标标记

    public MyArrayQueue(){
        this.objs = new Object[INIT_CAPACITY];
    }
    public MyArrayQueue(int initCapacity){
        if (initCapacity < 1 || initCapacity > MAX_CAPACITY){
            throw new IllegalArgumentException("initCapacity = " + initCapacity);
        }
        this.objs = new Object[initCapacity];
    }

    /**
     * 队列的入队列操作
     * @param value: 要入队列的内容
     * @return: 入队列是否成功
     */
    public boolean offer(T value){
        // 判断底层这个容纳数据的数组, 是否慢了
        if (size == objs.length){
            int newLen = getLen();
            grow(newLen);
        }
        // 添加.

        // 添加到尾标记位置
        objs[end] = value;
        // 添加完成之后, 让尾标记"逻辑后移"
        end = (end + 1) % objs.length;

        size++;
        return true;
    }
    // 根据指定长度扩容数组
    private void grow(int newLen) {
        // 新数组
        Object[] newObjs = new Object[newLen];

        // 转移旧数组数据:   逻辑转移
        for (int i = 0; i < objs.length; i++) {
            int tag = (head + i) % objs.length;

            newObjs[i] = objs[tag];
        }

        objs = newObjs;
        head = 0;
        end = size;
    }
    // 根据旧数组长度获取一个新长度
    private int getLen() {
        int oldLen = objs.length;
        int newLen = oldLen << 1;

        if (newLen < 0 || newLen > MAX_CAPACITY){
            newLen = MAX_CAPACITY;
        }

        if (oldLen == newLen){
            throw new RuntimeException("stack is full");
        }

        return newLen;
    }


    /**
     * 队列的出队列操作
     * @return: 被删除的队头
     */
    public T poll(){
        if (isEmpty()){
            throw new RuntimeException("queue is empty");
        }
        // 不空

//        if (size == 1){
//            T oldValue = (T) objs[head];
//
//            head = 0;
//            end = 0;
//            size--;
//            return oldValue;
//        }



        // 拿到头位置的数据
        T oldValue = (T) objs[head];
        // 让头标记逻辑后移
        head = (head + 1) % objs.length;

        size--;
        return oldValue;
    }

    /**
     * 查看队头数据
     * @return: 返回队头数据
     */
    public T peek(){
        if (isEmpty()){
            throw new RuntimeException("queue is empty");
        }

        // 不空
        return  (T)objs[head];
    }

    public boolean isEmpty(){
        return size == 0;
    }
    // 入队列: offer
    // 出队列: poll
    // 查看队头数据: peek

}
